{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find The Original Array of Prefix Xor"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #array"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findArray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出前缀异或的原始数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的 <strong>整数</strong> 数组 <code>pref</code> 。找出并返回满足下述条件且长度为 <code>n</code> 的数组<em> </em><code>arr</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>pref[i] = arr[0] ^ arr[1] ^ ... ^ arr[i]</code>.</li>\n",
    "</ul>\n",
    "\n",
    "<p>注意 <code>^</code> 表示 <strong>按位异或</strong>（bitwise-xor）运算。</p>\n",
    "\n",
    "<p>可以证明答案是 <strong>唯一</strong> 的。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>pref = [5,2,0,3,1]\n",
    "<strong>输出：</strong>[5,7,2,3,2]\n",
    "<strong>解释：</strong>从数组 [5,7,2,3,2] 可以得到如下结果：\n",
    "- pref[0] = 5\n",
    "- pref[1] = 5 ^ 7 = 2\n",
    "- pref[2] = 5 ^ 7 ^ 2 = 0\n",
    "- pref[3] = 5 ^ 7 ^ 2 ^ 3 = 3\n",
    "- pref[4] = 5 ^ 7 ^ 2 ^ 3 ^ 2 = 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>pref = [13]\n",
    "<strong>输出：</strong>[13]\n",
    "<strong>解释：</strong>pref[0] = arr[0] = 13\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= pref.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= pref[i] &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-original-array-of-prefix-xor](https://leetcode.cn/problems/find-the-original-array-of-prefix-xor/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-original-array-of-prefix-xor](https://leetcode.cn/problems/find-the-original-array-of-prefix-xor/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[5,2,0,3,1]', '[13]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: list[int]) -> list[int]:\n",
    "        ans = [0]*len(pref)\n",
    "        ans[0] = pref[0]\n",
    "        for i in range(1, len(pref)):\n",
    "            ans[i]=pref[i-1] ^ pref[i]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        for i in range(len(pref)-1, 0, -1):\n",
    "            pref[i] ^= pref[i-1]\n",
    "        return pref\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        #  a^b^b = a \n",
    "        for i in range(len(pref)-1,0,-1):\n",
    "            pref[i] = pref[i]^pref[i-1]\n",
    "        \n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        a = []\n",
    "        while len(pref) > 1:\n",
    "            i = pref.pop()\n",
    "            a.append(i ^ pref[-1])\n",
    "        a.append(pref.pop())\n",
    "        return a[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        n = len(pref)\n",
    "        if n == 1: return pref\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            pref[i] ^= pref[i - 1]\n",
    "        return pref\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        for i in range(len(pref)-1,0,-1):\n",
    "            pref[i] ^= pref[i-1]\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        n = len(pref)\n",
    "        for i in range(n - 1, 0, -1):\n",
    "            pref[i] = pref[i] ^ pref[i - 1]\n",
    "        return pref"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        arr = pref.copy()\n",
    "        p = arr[0]\n",
    "        for i in range(1, len(arr)):\n",
    "            arr[i] ^= p\n",
    "            p ^= arr[i]\n",
    "        return arr"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return [pref[0]] + [x ^ y for x, y in pairwise(pref)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        \n",
    "        n = len(pref)\n",
    "    \n",
    "        \n",
    "        for i in range(n-1,0,-1):\n",
    "            pref[i] = pref[i - 1] ^ pref[i]\n",
    "            \n",
    "        return pref\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        ll = len(pref)\n",
    "        ans = [0 for i in range(ll)]\n",
    "        ans[0] = pref[0]\n",
    "        for i in range(1,ll):\n",
    "            ans[i] = pref[i]^pref[i-1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return [pref[0]] + [x ^ y for x, y in pairwise(pref)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        n = len(pref)\n",
    "        ans =[pref[0]]* n\n",
    "        for i in range(1, n):\n",
    "            ans[i] = pref[i-1] ^ pref[i]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return map(xor, pref, [0] + pref[:-1])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        pre=[0]*(len(pref))\n",
    "        pre[0]=pref[0]\n",
    "        for i in range(len(pref)-1):\n",
    "            pre[i+1]=pref[i+1]^pref[i]\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        arr = [pref[0]]\n",
    "        for (x,y) in pairwise(pref):\n",
    "            arr.append(x ^ y)\n",
    "        return arr\n",
    "\n",
    "'''\n",
    "按位异或的性质：A xor B = C 则 A xor C = B \n",
    "同时由于前缀在继承：ans[i] = pref[i] ^ pref[i - 1]\n",
    "'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# -*- coding: utf-8 -*-\n",
    "'''\n",
    "@author: xxf\n",
    "@file: 2433\n",
    "@time: 2023/4/21 15:26\n",
    "'''\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        r=[pref[0]]\n",
    "        for i in range(len(pref)-1):\n",
    "            r.append(pref[i]^pref[i+1])\n",
    "        return r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return [pref[0]] + [x ^ y for x, y in pairwise(pref)]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return [pref[0]] + [x ^ y for x, y in pairwise(pref)]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        return [pref[0]] + [curr ^ next for curr, next in pairwise(pref)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findArray(self, pref: List[int]) -> List[int]:\n",
    "        res=[pref[0]]\n",
    "        for i in range(1,len(pref)):\n",
    "            res.append(pref[i-1]^pref[i])\n",
    "        return res"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
